package algo.A05_其他排序算法;

import util.ArrayUtil;

import java.util.Scanner;

public class T03_前k个数_堆排序优化 {
    private static int[] heap;//堆
    private static int size = 0;//堆中的元素个数，初始化为0
    private static int k;//前k个数

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("k = ");
        k = sc.nextInt();//前k个数
        heap = new int[k];
        System.out.println("请开始输入数据：");
        int x = sc.nextInt();//开始输入数据
        while (x != -1) {
            solution(x);
            ArrayUtil.print(heap);
            x = sc.nextInt();
        }
    }

    /**
     * 如果数量小于等于k，直接放入堆中
     * 如果数量等于k，则进行堆化
     *
     * @param x
     */
    private static void solution(int x) {
        if (size < k) {
            heap[size++] = x;
            //容量达到K时进行堆化
            if (size == k) {
                //构建一个堆
                build_maxHeap(heap);
            }
        }
        //x和堆顶元素进行比较，如果x小于堆顶，则x将挤掉堆顶的元素并向下调整
        //PS:堆顶是最大的，放进来的更小当然要把最大的给挤掉
        else if (x < heap[0]) {
            heap[0] = x;
            heapify(heap, 0, k);
        }
    }

    /**
     * 构建大顶堆
     *
     * @param arr
     */
    private static void build_maxHeap(int[] arr) {
        //从最后一个结点的父结点开始heapify
        for (int i = (arr.length - 1) / 2; i >= 0; i--) {
            heapify(arr, i, arr.length);
        }
    }

    /**
     * 维护堆的性质(大顶堆)
     *
     * @param arr
     * @param root
     * @param length
     */
    private static void heapify(int[] arr, int root, int length) {
        int max_index = root;//假设根节点就是最大的
        int lChild = root * 2 + 1;
        int rChild = root * 2 + 2;
        if (lChild < length && arr[lChild] > arr[max_index]) {
            max_index = lChild;
        }
        if (rChild < length && arr[rChild] > arr[max_index]) {
            max_index = rChild;
        }
        if (max_index != root) {
            ArrayUtil.swap(arr, max_index, root);
            heapify(arr, max_index, length);
        }
    }
}
